/*
 * Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a <= b <= c)
The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)
 */
package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ThreeSum {
	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> tripList = new ArrayList<ArrayList<Integer>>();
        Set<ArrayList<Integer>> trip = new HashSet<ArrayList<Integer>>();
        
        if(num.length < 3)
            return tripList;
            
         int zero = 0;
         List<Integer> neg = new ArrayList<Integer>();
         List<Integer> pos = new ArrayList<Integer>();
         Set<Integer> numSet = new HashSet<Integer>();
         
         for(int i = 0; i < num.length; i++)
         {
            numSet.add(num[i]);
            if(num[i] < 0)
                neg.add(num[i]);
            else if(num[i] > 0)
                pos.add(num[i]);
            else
                zero++;
         }
         
         Collections.sort(pos);
         Collections.sort(neg);
         Set<List<Integer>> twoPosSet = new HashSet<List<Integer>>();
         Set<List<Integer>> twoNegSet = new HashSet<List<Integer>>();
         for(int i = 0; i < pos.size(); i++)
         {
             for(int j = i + 1; j < pos.size(); j++)
             {
                 List<Integer> twoPos = new ArrayList<Integer>();
                 twoPos.add(pos.get(i));
                 twoPos.add(pos.get(j));
                 twoPosSet.add(twoPos);
             }
         }
         for(int i = 0; i < neg.size(); i++)
         {
             for(int j = i + 1; j < neg.size(); j++)
             {
                 List<Integer> twoNeg = new ArrayList<Integer>();
                 twoNeg.add(neg.get(i));
                 twoNeg.add(neg.get(j));
                 twoNegSet.add(twoNeg);
             }
         }
         
         
         
         
         if(zero >= 3)
         {
             ArrayList<Integer> zTrip = new ArrayList<Integer>();
             zTrip.add(0); zTrip.add(0); zTrip.add(0);
             trip.add(zTrip);
         }
         
         for(List<Integer> twoPos : twoPosSet)
         {
             int sum = twoPos.get(0) + twoPos.get(1);
             if(numSet.contains(0 - sum))
            {
                ArrayList<Integer> aTrip = new ArrayList<Integer>();
                aTrip.add(0 - sum);
                aTrip.addAll(twoPos);
                trip.add(aTrip);
            }
         }
         for(List<Integer> twoNeg : twoNegSet)
         {
             int sum = twoNeg.get(0) + twoNeg.get(1);
             if(numSet.contains(0 - sum))
             {
                 ArrayList<Integer> aTrip = new ArrayList<Integer>();
                 aTrip.addAll(twoNeg);
                 aTrip.add(0 - sum);
                 trip.add(aTrip);
             }
         }
         
         if(zero >= 1)
         {
             for(int i = 0; i < neg.size(); i++)
                for(int j = 0; j < pos.size(); j++)
                {
                    if(neg.get(i) + pos.get(j) == 0)
                    {
                        ArrayList<Integer> aTrip = new ArrayList<Integer>();
                        aTrip.add(neg.get(i));
                        aTrip.add(0);
                        aTrip.add(pos.get(j));
                        trip.add(aTrip);
                    }
                }
         }
         
         tripList.addAll(trip);
         return tripList;
    }
}
